package leetcode_hot100;

import java.util.*;

public class Demo2 {
    // 98. 验证二叉搜索树
    TreeNode prev = null;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;

        if(!isValidBST(root.left)) return false;
        if(prev != null && prev.val >= root.val) return false;
        prev = root;
        return isValidBST(root.right);
    }



    //153. 寻找旋转排序数组中的最小值
    public int findMin(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1, mid;
        while(left < right) {
            mid = left + (right - left) / 2;
            if(nums[mid] > nums[n - 1]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }



    //24. 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        ListNode cur = head, next = cur.next;
        while (cur != null && next != null) {
            cur.next = next.next;
            tail.next = next;
            next.next = cur;
            tail = cur;
            cur = cur.next;
            if(cur != null) next = cur.next;
        }
        return newHead.next;
    }



    //62. 不同路径
    public int uniquePaths(int m, int n) {
        // 动态规划：dp[i][j]表示以(0, 0)为起点，(i, j)为终点，共有多少种方式可以到达
        int[][] dp = new int[m + 1][n + 1];
        dp[1][0] = 1;

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m][n];
    }



    //21. 合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode newHead = new ListNode();
        ListNode t = newHead;
        while(list1 != null && list2 != null) {
            if(list1.val <= list2.val) {
                t.next = list1;
                list1 = list1.next;
            } else {
                t.next = list2;
                list2 = list2.next;
            }
            t = t.next;
        }
        if(list1 != null) t.next = list1;
        if(list2 != null) t.next = list2;
        return newHead.next;
    }




    //2. 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        int carry = 0;

        while(l1 != null || l2 != null || carry > 0) {
            if(l1 != null) {
                carry += l1.val;
                l1 = l1.next;
            }
            if(l2 != null) {
                carry += l2.val;
                l2 = l2.next;
            }
            ListNode node = new ListNode(carry % 10);
            tail.next = node;
            tail = tail.next;
            carry /= 10;
        }

        return newHead.next;
    }



    //102. 二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()) {
            int sz = q.size();
            List<Integer> tmp = new ArrayList<>();
            while(sz-- > 0) {
                TreeNode node = q.poll();
                tmp.add(node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
            }
            ret.add(tmp);
        }
        return ret;
    }




    //560. 和为 K 的子数组
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1);

        int sum = 0, ret = 0;
        for(int x : nums) {
            sum += x;
            if(hash.containsKey(sum - k)) ret += hash.get(sum - k);
            hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        }

        return ret;
    }



    //148. 排序链表
    public ListNode sortList(ListNode head) {
        return mergeSort(head, null);
    }

    public ListNode mergeSort(ListNode head, ListNode tail) {
        if(head == null ) return null;
        if(head == tail) {
            head.next = null;
            return head;
        }

        ListNode fast = head, slow = head;  // 寻找该排序区间链表的中点
        while(fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode list1 = mergeSort(slow.next, tail);     // 必须将此步骤放在前面，因为先得到cur1的话，slow.next 会被置空
        ListNode list2 = mergeSort(head, slow);

        return mergeList(list1, list2);
    }

    public ListNode mergeList(ListNode cur1, ListNode cur2) {
        ListNode tmpHead = new ListNode();
        ListNode rear = tmpHead;
        while(cur1 != null && cur2 != null) {
            if(cur1.val <= cur2.val) {
                rear.next = cur1;
                cur1 = cur1.next;
            } else {
                rear.next = cur2;
                cur2 = cur2.next;
            }
            rear = rear.next;
        }

        if(cur1 != null) rear.next = cur1;
        if(cur2 != null) rear.next = cur2;
        return tmpHead.next;
    }



    // 438. 找到字符串中所有字母异位词
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int m = s.length(), n = p.length();
        if(m < n) return ret;

        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for(char ch : p.toCharArray()) hash1[ch - 'a']++;

        int count = 0;
        for(int left = 0, right = 0; right < m; right++) {
            int index = s.charAt(right) - 'a';
            hash2[index]++;
            if(hash1[index] > 0 && hash2[index] <= hash1[index]) count++;

            if(right - left + 1 == n) {
                if(count == n) ret.add(left);
                char ch = s.charAt(left);
                if(hash1[ch - 'a'] > 0 && hash2[ch - 'a'] <= hash1[ch - 'a']) count--;
                hash2[s.charAt(left++) - 'a']--;
            }
        }
        return ret;
    }



    // 239. 滑动窗口最大值
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if(n < k) return new int[0];

        int[] ret = new int[n - k + 1];
        Deque<Integer> q = new LinkedList<>();
        for(int left = 0, right = 0, index = 0; right < n; right++) {
            int num = nums[right];
            while(!q.isEmpty() && num > q.peekLast()) {
                q.pollLast();
            }
            q.addLast(num);

            if(right - left + 1 == k) {
                ret[index++] = q.peekFirst();
                if(nums[left++] == q.peekFirst()) q.pollFirst();
            }
        }
        return ret;
    }


    // 128. 最长连续序列
    public int longestConsecutive(int[] nums) {
        // K-V: num - num所在区间的最长序列
        Map<Integer, Integer> hash = new HashMap<>();

        int ret = 0;
        for(int x : nums) {
            if(hash.get(x) == null) {
                int left = hash.getOrDefault(x - 1, 0);
                int right = hash.getOrDefault(x + 1, 0);
                int len = 1 + left + right;
                ret = Math.max(ret, len);
                hash.put(x, len);
                hash.put(x - left, len);
                hash.put(x + right, len);
            }
        }
        return ret;
    }


    // 16. 最接近的三数之和
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int absoluteGap = Integer.MAX_VALUE, ret = 0, n = nums.length;

        for(int i = 0; i < n - 2; i++) {
            for(int left = i + 1, right = n - 1; left < right; ) {
                int sum = nums[i] + nums[left] + nums[right];
                if(Math.abs(sum - target) < absoluteGap) {
                    ret = sum;
                    absoluteGap = (int)(Math.abs(sum - target));
                }
                if(sum == target) return ret;
                else if(sum > target) right--;
                else left++;
            }
        }
        return ret;
    }



    // 108. 将有序数组转换为二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        return convertBBSTree(nums, 0, nums.length - 1);
    }
    public TreeNode convertBBSTree(int[] nums, int left, int right) {
        if(left > right) return null;

        int mid = (left + right) / 2;       // 每次取范围内的中点，将左右子树结点数量平均分配
        TreeNode root = new TreeNode(nums[mid]);
        root.left = convertBBSTree(nums, left, mid - 1);
        root.right = convertBBSTree(nums, mid + 1, right);
        return root;
    }


    // 78. 子集
    List<List<Integer>> ret;
    List<Integer> path;

    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();

        dfs(nums, 0);
        return ret;
    }
    private void dfs(int[] nums, int pos) {
        ret.add(new ArrayList<>(path));
        if(pos == nums.length) return;

        for(int i = pos; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }




    //5. 最长回文子串
    public String longestPalindrome(String s) {
        int n = s.length();
        int start = 0, end = 0;

        for(int i = 0; i < n - 1; i++) {
            int left = i - 1, right = i + 1;
            for( ; left >= 0 && right < n && s.charAt(left) == s.charAt(right); left--, right++);
            int tmpStart = left + 1, tmpEnd = right - 1;
            for(left = i, right = i + 1; left >= 0 && right < n && s.charAt(left) == s.charAt(right); left--, right++);

            if(right - left - 1 > tmpEnd - tmpStart + 1) {
                tmpStart = left + 1;
                tmpEnd = right - 1;
            }
            if(tmpEnd - tmpStart + 1 > end - start + 1) {
                start = tmpStart;
                end = tmpEnd;
            }
        }
        return s.substring(start, end + 1);
    }



    //64. 最小路径和
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];

        for(int i = 2; i <= m; i++) dp[i][0] = Integer.MAX_VALUE;
        for(int j = 1; j <= n; j++) dp[0][j] = Integer.MAX_VALUE;

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }



    //1143. 最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        // 选取第一个字符串 0 ~ i 区间以及 第二个字符串 0 ~ j 区间作为研究对象
        // dp[i][j]: 第一个字符串 0 ~ i 区间以及 第二个字符串 0 ~ j 区间所有子序列中 最长公共子序列的长度
        int m = text1.length(), n = text2.length();
        text1 = " " + text1; text2 = " " + text2;
        int[][] dp = new int[m + 1][n + 1];

        for(int i = 1; i <= m; i++) {       // 从上往下，从左往右
            for(int j  = 1; j <= n; j++) {
                if(text1.charAt(i) == text2.charAt(j)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[m][n];
    }



    // 322. 零钱兑换
    public int coinChange(int[] coins, int amount) {
        // dp[i][j]: 从前 i 中硬币中恰好凑成金额为 j 的最少硬币个数
        int n = coins.length, INF = 0X3f3f3f3f;
        int[] dp = new int[amount + 1];
        for(int j = 1; j <= amount; j++) dp[j] = INF;

        for(int i = 1; i <= n; i++) {
            for(int j = coins[i - 1]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        if(dp[amount] >= INF) return -1;
        return dp[amount];
    }



    // 32. 最长有效括号
    public int longestValidParentheses(String s) {
        // dp[i]: 以 i 位置为结尾且 i 位置字符为 ) 的所有子串中最长子串的长度
        int n = s.length();
        int[] dp = new int[n + 1];
        s = " " + s;

        int ret = 0;
        for(int i = 2; i <= n; i++) {
            char ch = s.charAt(i);
            if(ch == ')') {
                if(s.charAt(i - 1) == '(') dp[i] = dp[i - 2] + 2;
                else {
                    if(s.charAt(i - dp[i - 1] - 1) == '(') dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }


    // LCP 30. 魔塔游戏
    public int magicTower(int[] nums) {
        long sum = 1, n = nums.length;
        for(int x : nums) sum += x;
        if(sum <= 0) return -1;

        PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> nums[o1] - nums[o2]);
        int cur = 0, ret = 0;
        for(sum = 1; cur < n; cur++) {
            if(nums[cur] < 0) heap.add(cur);
            sum += nums[cur];
            if(sum <= 0) {
                sum -= nums[heap.poll()];
                ret++;
            }
        }
        return ret;
    }


    // 226. 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return root;

        TreeNode leftTree = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(leftTree);
        return root;
    }



    // 17. 电话号码的字母组合
    List<String> ret8;
    StringBuilder path8;
    String[] flag = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        ret = new ArrayList<>();
        if(digits.isEmpty()) return ret8;
        path8 = new StringBuilder();

        dfs(digits, 0);
        return ret8;
    }
    private void dfs(String s, int pos) {
        if(pos == s.length()) {
            ret8.add(path8.toString());
            return;
        }

        int index = s.charAt(pos) - '0';
        for(int i = 0; i < flag[index].length(); i++) {
            path8.append(flag[index].charAt(i));
            dfs(s, pos + 1);
            path8.deleteCharAt(path8.length() - 1);
        }
    }


    // 739. 每日温度
    public int[] dailyTemperatures(int[] t) {
        int n = t.length;
        int[] answer = new int[n];
        Deque<Integer> st = new LinkedList<>();

        for(int i = 0; i < n; i++) {
            while(!st.isEmpty() && t[i] > t[st.peek()]) {
                int index = st.pop();
                answer[index] = i - index;
            }
            st.push(i);
        }
        return answer;
    }




    //2641. 二叉树的堂兄弟节点 II
    public TreeNode replaceValueInTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        int sum = root.val;
        while(!q.isEmpty()) {
            int sz = q.size(), nextSum = 0;
            while(sz-- > 0) {
                TreeNode f = q.poll();
                f.val = sum - f.val;
                if(f.left != null && f.right != null) {
                    f.left.val = f.left.val + f.right.val;
                    f.right.val = f.left.val;
                    q.offer(f.left);
                    q.offer(f.right);
                    nextSum += f.left.val;
                } else if(f.left != null) {
                    q.offer(f.left);
                    nextSum += f.left.val;
                } else if(f.right != null) {
                    q.offer(f.right);
                    nextSum += f.right.val;
                }
            }
            sum = nextSum;
        }
        return root;
    }



    // 15. 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ret = new ArrayList<>();

        for(int i = 0; i < n - 2; i++) {
            // 跳过重复元素
            while(i > 0 && i < n - 2 && nums[i] == nums[i - 1]) i++;
            int aim = -nums[i];
            for(int left = i + 1, right = n - 1; left < right; ) {
                if(nums[left] + nums[right] == aim) {
                    ret.add(Arrays.asList(nums[i], nums[left++], nums[right--]));
                    // 跳过重复元素
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
                else if(nums[left] + nums[right] < aim) left++;
                else right--;
            }
        }
        return ret;
    }



    // 11. 盛最多水的容器
    public int maxArea(int[] height) {
        int n = height.length, ret = 0;
        for(int left = 0, right = n - 1; left < right; ) {
            int v = (right - left) * Math.min(height[left], height[right]);
            if(v > ret) ret = v;
            if(height[left] < height[right]) left++;
            else right--;
        }
        return ret;
    }



    // 3. 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        int[] hash = new int[128];
        int ret = 0, left = 0, right = 0;

        while(right < s.length()) {
            char ch = s.charAt(right++);
            hash[ch]++;

            while(hash[ch] > 1) {
                hash[s.charAt(left++)]--;
            }
            ret = Math.max(ret, right - left);
        }
        return ret;
    }




    // 206. 反转链表
    public ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        while(head != null) {
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
        }
        return newHead;
    }



    // 25. K 个一组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1) return head;
        // 1. 得到需要翻转的组数
        int count = 0;
        for(ListNode cur = head; cur != null; cur = cur.next) count++;
        count /= k;

        // 2. 进行 count次翻转，每次翻转 k 个结点
        ListNode newHead = new ListNode();
        ListNode tail = newHead, cur = head;
        while(count-- > 0) {
            ListNode tmpHead = null, tmp = cur;
            for(int i = 0; i < k; i++) {
                ListNode next = cur.next;
                cur.next = tmpHead;
                tmpHead = cur;
                cur = next;
            }
            tail.next = tmpHead;
            tail = tmp;
        }
        // 3. 处理不用翻转的剩余结点
        tail.next = cur;
        return newHead.next;
    }



    // 23. 合并 K 个升序链表
    public ListNode mergeKLists(ListNode[] lists) {
        // 归并排序
        if(lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int left, int right) {
        if(left >= right) return lists[left];

        int mid = (left + right) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);

        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        if(l1 != null) tail.next = l1;
        if(l2 != null) tail.next = l2;
        return newHead.next;
    }



    // 42. 接雨水
    public int trap(int[] height) {
        // 1. 动态规划dp[i]: 前 i-1 个数中柱子的最大高度,dp2[i]: i 位置后柱子的最大高度
        int n = height.length;
        int[] dp1 = new int[n], dp2 = new int[n];
        for(int i = 1; i < n; i++) dp1[i] = Math.max(height[i - 1], dp1[i - 1]);
        for(int i = n - 2; i >= 0; i--) dp2[i] = Math.max(height[i + 1], dp2[i + 1]);

        int ret = 0;
        for(int i = 1; i < n - 1; i++) {
            if(dp1[i] - height[i] > 0 && dp2[i] - height[i] > 0) ret += Math.min(dp1[i], dp2[i]) - height[i];
        }
        return ret;
    }




    // 101. 对称二叉树
    public boolean isSymmetric(TreeNode root) {
        return isChildSymmetric(root.left, root.right);
    }
    public boolean isChildSymmetric(TreeNode leftTree, TreeNode rightTree) {
        if(leftTree == null && rightTree == null) return true;
        if(leftTree == null || rightTree == null) return false;
        if(leftTree.val != rightTree.val) return false;

        return isChildSymmetric(leftTree.left, rightTree.right) && isChildSymmetric(leftTree.right, rightTree.left);
    }



    // 437. 路径总和 III
    int ret9;
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null) return 0;
        dfs(root, (long)targetSum);
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return ret9;
    }
    public void dfs(TreeNode root, long targetSum) {
        if(root == null) return;
        targetSum -= root.val;
        if(targetSum == 0) {
            ret9++;
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
    }




    // 394. 字符串解码
    public String decodeString(String _s) {
        Deque<StringBuilder> strSt = new ArrayDeque<>();
        Deque<Integer> intSt = new ArrayDeque<>();
        strSt.push(new StringBuilder(""));
        char[] s = _s.toCharArray();
        int i = 0, n = s.length;

        while(i < n) {
            if(s[i] >= '0' && s[i] <= '9') {    // 遇到数字，提取数字放入数组栈
                int tmp = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9') {
                    tmp = tmp * 10 + (s[i++] - '0');
                }
                intSt.push(tmp);
            } else if(s[i] == '[') {            // 遇到 [ 括号，提取里面的字符串,入栈
                i++;
                StringBuilder tmp = new StringBuilder();
                while(i < n && s[i] >= 'a' && s[i] <= 'z') {
                    tmp.append(s[i++]);
                }
                strSt.push(tmp);
            } else if(s[i] == ']') {            // 遇到 ] 括号，重复字符串，并拼接到栈顶元素的后面
                i++;
                StringBuilder tmp = new StringBuilder();
                StringBuilder copy = strSt.pop();
                for(int count = intSt.pop(); count > 0; count--) {
                    tmp.append(copy);
                }
                strSt.push(strSt.pop().append(tmp));
            } else {                            // 遇到普通字符串，提取字符串，拼接到栈顶元素的后面
                StringBuilder tmp = new StringBuilder();
                while(i < n && s[i] >= 'a' && s[i] <= 'z') {
                    tmp.append(s[i++]);
                }
                strSt.push(strSt.pop().append(tmp));
            }
        }
        return strSt.pop().toString();
    }



    // 139. 单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> hash = new HashSet<>();
        hash.addAll(wordDict);

        // dp[i]: 从第 0 ~ i个字符能否由 字典中的单词拼接而成
        int n = s.length();
        s = " " + s;

        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for(int i = 1; i <= n; i++) {
            for(int j = i; j >= 1; j--) {
                if(dp[j - 1] && hash.contains(s.substring(j, i + 1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }



    // 300. 最长递增子序列
    public int lengthOfLIS(int[] nums) {
        // dp[i]: 以 i 位置为结尾的所有子序列中最长子序列的长度
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        int ret = 1;
        for(int i = 1; i < n; i++) {
            for(int j = i - 1; j >= 0; j--) {
                if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }
}
